package com.zlk.algorithm.algorithm.dynamicPlan.threeDimension;

// 盈利计划(多维费用背包)
// 集团里有 n 名员工，他们可以完成各种各样的工作创造利润
// 第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与
// 如果成员参与了其中一项工作，就不能参与另一项工作
// 工作的任何至少产生 minProfit 利润的子集称为 盈利计划
// 并且工作的成员总数最多为 n
// 有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
// 测试链接 : https://leetcode.cn/problems/profitable-schemes/
public class Code02_ProfitableSchemes {


    public static void main(String[] args) {
        Code02_ProfitableSchemes test = new Code02_ProfitableSchemes();
        test.profitableSchemes(10,5,new int[]{2,3,5},new int[]{6,7,8});
    }

    /**
     *
     * @param n
     * @param minProfit
     * @param group
     * @param profit
     * @return
     */

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        //return f1(group, profit, 0, n, minProfit);
        //return f2(group, profit, n, minProfit);
        //return f3(group, profit, n, minProfit);
        return profitableSchemes3(n,minProfit,group,profit);

    }

    private int f3(int[] g, int[] p, int n, int m) {
        int[][] dp = new int[n+1][m+1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;// 工作耗尽了，之前可能选了一些工作
        }
        for (int i = p.length-1; i >=0 ; i--) {
            dp[0][0] =1;
            for (int r = n; r >=1 ; r--) {
                for (int s = m; s >=0 ; s--) {
                    dp[r][s] = dp[r][s];
                    int p2 = 0;
                    if(g[i]<=r){
                        if(s-p[i]<=0){
                            p2 = dp[r-g[i]][0];
                        }else{
                            p2 = dp[r-g[i]][s-p[i]];
                        }
                        dp[r][s]+=p2;
                        dp[r][s]%=mod;
                    }
                }
            }
        }
        return dp[n][m];
    }

    //本质与f3一样只是写法优化
    public  int profitableSchemes3(int n, int minProfit, int[] group, int[] profit) {
        // i = 没有工作的时候，i == g.length
        int[][] dp = new int[n + 1][minProfit + 1];
        for (int r = 0; r <= n; r++) {
            dp[r][0] = 1;
        }
        int m = group.length;
        for (int i = m - 1; i >= 0; i--) {
            for (int r = n; r >= 0; r--) {
                for (int s = minProfit; s >= 0; s--) {
                    int p1 = dp[r][s];
                    int p2 = group[i] <= r ? dp[r - group[i]][Math.max(0, s - profit[i])] : 0;
                    dp[r][s] = (p1 + p2) % mod;
                }
            }
        }
        return dp[n][minProfit];
    }


    public  int mod = 1000000007;
    // n 人  m 利润
    private int f2(int[] g, int[] p, int n, int m) {
        int[][][] dp = new int[p.length+1][n+1][m+1];
        for (int i = 0; i <= p.length; i++) {
            dp[i][0][0] =1;// 人已经耗尽了，之前可能选了一些工作
        }
        for (int i = 0; i <= n; i++) {
            dp[p.length][i][0] = 1;// 工作耗尽了，之前可能选了一些工作
        }
        for (int i = p.length-1; i >=0 ; i--) {
            for (int r = 1; r <= n; r++) {
                for (int s=0; s <= m; s++) {
                    dp[i][r][s] = dp[i+1][r][s];
                    int p2 = 0;
                    if(g[i]<=r){
                        if(s-p[i]<=0){
                            p2 = dp[i+1][r-g[i]][0];
                        }else{
                            p2 = dp[i+1][r-g[i]][s-p[i]];
                        }
                        dp[i][r][s]+=p2;
                        dp[i][r][s]%=mod;
                    }
                }
            }
        }
        return dp[0][n][m];
    }

    // i : 来到i号工作
    // r : 员工额度还有r人，如果r<=0说明已经没法再选择工作了
    // s : 利润还有s才能达标，如果s<=0说明之前的选择已经让利润达标了
    // 返回 : i.... r、s，有多少种方案
    public static int f1(int[] g, int[] p, int i, int r, int s) {
        if (r <= 0) {
            // 人已经耗尽了，之前可能选了一些工作
            return s <= 0 ? 1 : 0;
        }
        // r > 0
        if (i == g.length) {
            // 工作耗尽了，之前可能选了一些工作
            return s <= 0 ? 1 : 0;
        }
        // 不要当前工作
        int p1 = f1(g, p, i + 1, r, s);
        // 要做当前工作
        int p2 = 0;
        if (g[i] <= r) {
            p2 = f1(g, p, i + 1, r - g[i], s - p[i]);
        }
        return p1 + p2;
    }

    private int f1Myself( int minProfit, int[] group, int[] profit, int i,int n) {
        //base case
//        if(minProfit<=0){  为啥这个不对，是因为是题目是要求是最要求的利润，达到之后还可以继续选择
//            return 1;
//        }
//        if(i==profit.length||n<=0){
//            return 0;
//        }

        if(n<=0){
            return minProfit<=0?1:0;
        }
        if(i==profit.length){
            return minProfit<=0?1:0;
        }
        //不要
        int ans = f1Myself(minProfit, group, profit, i + 1, n);
        //要
        if(n-group[i]>=0){
            ans+=f1Myself(minProfit-profit[i],group,profit,i+1,n-group[i]);
        }
        return ans;
    }

}
